#!/usr/bin/env python
# coding=utf-8
"""
https://leetcode.com/problems/container-with-most-water/description/
n方复杂度的就别写了: max(min(x,y) * (x_index - y_index))

"""


def maxArea(heights):
    hlen = len(heights)
    lp = 0
    rp = hlen - 1
    max_ar = (hlen - 1) * min(heights[0], heights[hlen - 1])
    while lp < rp:
        if heights[lp] > heights[rp]:
            # 移动rp
            new_rp = rp
            while heights[new_rp] <= heights[rp] and new_rp > lp:
                # print("move rp - 1")
                new_rp = new_rp - 1
            rp = new_rp
        else:
            # 移动lp
            new_lp = lp
            while heights[new_lp] <= heights[lp] and new_lp < rp:
                # print("move lp + 1")
                new_lp = new_lp + 1
            lp = new_lp

        new_max = min(heights[lp], heights[rp]) * (rp - lp)
        max_ar = new_max if new_max > max_ar else max_ar
        # print("max " + str(max_ar))

    return max_ar


if __name__ == '__main__':
    print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])) #49
    # print(maxArea([2, 3, 4, 5, 18, 17, 6])) #17
    # print(maxArea([2, 3, 10, 5, 7, 8, 9])) #36
    # print(maxArea([62, 4, 5, 60, 7, 8, 9])) # 180
